Slovarji II

Zbiranje osebnih podatkov

V nekem podjetju zbirajo podatke o osebah, ki brskajo po medmrežju. Podatki so shranjeni v slovarjih (en slovar za vsako osebo). Ključ v takem slovarju je lastnost, vrednosti pa podatek o tej lastnosti za določeno osebo. Primeri takšnih slovarjev:

oseba1 = {'ime': 'Božidar', 'telefon': '031918211',
          'obiskane spletne strani': ['facebook.com', 'google.com']}
oseba2 = {'naslov': 'Dunajska 105', 'številka noge': 42,
          'prijatelji': ['Marko', 'Ana']}

1. podnaloga

Sestavite funkcijo podatek(oseba, lastnost), ki vrne podatek o lastnosti lastnost, ki ga imamo v slovarju oseba. Funkcija naj vrne None, če se ta podatek v slovarju ne nahaja. Primer:

>>> podatek({'ime': 'Božidar', 'naslov': 'Dunajska 105'}, 'naslov')
'Dunajska 105'
>>> podatek({'ime': 'Božidar', 'naslov': 'Dunajska 105'}, 'prijatelji')
None

Pri tem ne smeš uporabiti get!

Uradna rešitev

def podatek(oseba, lastnost):
    '''Vrne podatek o lastnosti lastnost oz. None'''
    if lastnost not in oseba:
        return None
    return oseba[lastnost]

2. podnaloga

Sestavite funkcijo podatekGet(oseba, lastnost), ki vrne podatek o lastnosti lastnost, ki ga imamo v slovarju oseba. Funkcija naj vrne None, če se ta podatek v slovarju ne nahaja. Primer:

>>> podatekGet({'ime': 'Božidar', 'naslov': 'Dunajska 105'}, 'naslov')
'Dunajska 105'
>>> podatekGet({'ime': 'Božidar', 'naslov': 'Dunajska 105'}, 'prijatelji')
None

Pri tem si nujno pomagajte z metodo get

Uradna rešitev

def podatekGet(oseba, lastnost):
    '''Vrne podatek o lastnosti lastnost oz. None'''
    return oseba.get(lastnost, None)

3. podnaloga

Za osebi oseba1 in oseba2 pravimo, da se ujemata v lastnosti lastnost, če za obe osebi poznamo podatka o tej lastnosti in sta podatka enaka. Če pa za obe osebi poznamo podatka in sta podatka različna, pa pravimo, da se osebi razlikujeta v lastnosti lastnost. Na primer, osebi

oseba1 = {'ime': 'Janez', 'priimek': 'Novak'}
oseba2 = {'ime': 'Jože', 'priimek': 'Novak', 'starost': 20}

se ujemata v lastnosti 'priimek' in razlikujeta v lastnosti 'ime'. (V lastnosti 'starost' se niti ne ujemata niti ne razlikujeta.)

Sestavite funkcijo ujemanje(oseba1, oseba2), ki pove, v koliko lastnostih se osebi oseba1 in oseba2 ujemata in v koliko lastnostih se razlikujeta. Rezultat naj funkcija vrne kot seznam z dvema elementoma. Primer:

>>> ujemanje({'ime': 'Janez', 'priimek': 'Novak'},
             {'ime': 'Jože', 'priimek': 'Novak', 'starost': 20})
[1, 1]

Uradna rešitev

def ujemanje(oseba1, oseba2):
    '''V koliko lastnostih se osebi ujemata in razlikujeta'''
    ujema = 0
    razlikuje = 0
    for lastnost in oseba1: # preverimo vse lastnosti prve osebe
        if lastnost in oseba2: # če gre za skupno lastnost
            if oseba1[lastnost] == oseba2[lastnost]:
                ujema += 1
            else:
                razlikuje += 1
    return [ujema, razlikuje]

4. podnaloga

Dva različna slovarja oseba1 in oseba2 lahko predstavljata isto osebo. To se zgodi, če se slovarja ne razlikujeta v več kot 1 lastnosti in se ujemata vsaj v 3 lastnostih ali če sta v obeh slovarjih lastnosti ime in priimek enaki. Na primer, slovarja

oseba1 = {'ime': 'Janez', 'priimek': 'Novak', 'telefon': '031123234',
          'starost': 90}
oseba2 = {'ime': 'Janez', 'priimek': 'Novak', 'davčna': '43424140'}

predstavljata isto osebo, prav tako slovarja

oseba1 = {'ime': 'Janez', 'priimek': 'Novak', 'telefon': '031123234',
          'starost': 90}
oseba2 = {'ime': 'Luka', 'priimek': 'Novak', 'starost': 90,
          'davčna': '43424140', 'telefon': '031123234'}

Sestavite funkcijo ista(oseba1, oseba2), ki preveri, ali slovarja predstavljata isto osebo. Na primer, za zgornja primera mora funkcija vrniti True.

Uradna rešitev

def ista(oseba1, oseba2):
    '''Ali gre ta isto osebo'''
    ujemata, razlikujeta = ujemanje(oseba1, oseba2) # uporaba funkcije prejšnje naloge
    je_ista = ujemata >= 3 and razlikujeta <= 1
    if je_ista :
        return True # dovolj je že ujemanje v lastnostih!
    # če ni ujemanja v lastnostih, preverimo ime in priimek
    if 'ime' in oseba1 and 'ime' in oseba2 and 'priimek' in oseba1 and 'priimek' in oseba2:
        je_ista = (oseba1['ime'] == oseba2['ime'] and oseba1['priimek'] == oseba2['priimek'])
    return je_ista

5. podnaloga

V seznamu slovarjev, ki predstavljajo osebe, se lahko zgodi, da več slovarjev predstavlja isto osebo (isto v smislu prejšnje podnaloge). V takem primeru pravimo, da so ti slovarji podvojeni.

Sestavite funkcijo podvojeni(s), ki vrne seznam vseh podvojenih slovarjev iz seznama s. Slovarji naj bodo razvrščeni v istem vrstnem redu kot v seznamu s. Primer:

>>> podvojeni([{'ime': 'Jan', 'priimek': 'Dan', 'naslov': 'Jadranska 21'},
               {'ime': 'Jan', 'priimek': 'Dan', 'naslov': 'Jadranska 19'},
               {'ime': 'Žan', 'priimek': 'Dan', 'naslov': 'Jadranska 21'},
               {'ime': 'Žan', 'priimek': 'Noč', 'naslov': 'Jamova 25'}])
[{'ime': 'Jan', 'priimek': 'Dan', 'naslov': 'Jadranska 21'},
 {'ime': 'Jan', 'priimek': 'Dan', 'naslov': 'Jadranska 19'}]

Uradna rešitev

def jeOsebaPodvojena(osb, s):
    '''Ali se oseba osb pojavi v seznamu s vsaj dvakrat'''
    kolikoIstih = 0
    for oseba2 in s: # pogledamo vse osebe slovarja s
        if ista(osb, oseba2): # gre za isto osebo po kriterijih prej
            kolikoIstih += 1
    return kolikoIstih >= 2

def podvojeni(s):
    '''Seznam vseh podvojenih oseb'''
    seznam = []
    for oseba in s: # vsako osebo 
        if jeOsebaPodvojena(oseba, s): # prevrimo, če je v seznamu oseba vsaj 2x
            seznam.append(oseba)
    return seznam

Kuhamo in pečemo

Sestavine, ki jih potrebujemo za nek recept, opišemo s slovarjem, v katerem so ključi sestavine, vrednosti pa količine, ki jih potrebujemo.

1. podnaloga

Sestavite funkcijo pomnozi(recept, faktor), ki sestavi in vrne nov recept. Ta naj vsebuje iste sestavine kot recept recept, le da so vse količine v njem pomnožene z danim faktorjem.

>>> pomnozi({'jajca': 4, 'moka': 500}, 2)
{'jajca': 8, 'moka': 1000}

Uradna rešitev

def pomnozi(recept, faktor):
    '''Vrne nov recept, spremenjen za faktor'''
    novR = dict()
    for sestavina, kolicina in recept.items():
        novR[sestavina] = kolicina * faktor
    return novR

def pomnoziV2(recept, faktor):
    '''Vrne nov recept, spremenjen za faktor'''
    # uporabimo izpeljane slovarje (dict comprehension)
    return {sestavina: kolicina * faktor for sestavina, kolicina in recept.items()}

2. podnaloga

Sestavite funkcijo imamoSestavine(recept, shramba), ki preveri, ali imamo v shrambi dovolj sestavin za dani recept. Sestavine, ki jih imamo v shrambi, so predstavljene s slovarjem na enak način kot sestavine v receptu.

Uradna rešitev

def imamoSestavine(recept, shramba):
    '''imamo v shrambi dovolj sestavin za dani recept'''
    for sestavina, kolicina in recept.items():
        if shramba.get(sestavina, -1) < kolicina: # uporaba get, da ne dobimo izjeme pri neobstoječih sestavinah
            return False # že če ena manjka, ne gre
    return True # vsega imamo dovolj!

3. podnaloga

Sestavite funkcijo potrebnoKupiti(recept, shramba), ki vrne slovar sestavin s pripadajočimi količinami, ki jih moramo še dokupiti, da bomo lahko skuhali jed po danem receptu.

>>> potrebnoKupiti({'jajca': 3, 'moka': 500}, {'moka': 1000, 'jajca': 6, 'sladkor': 1000})
{}
>>> potrebnoKupiti({'jajca': 3, 'moka': 500}, {'moka': 1000, 'sladkor': 1000})
{'jajca': 3}
>>> potrebnoKupiti({'jajca': 3, 'moka': 500}, {'moka': 100})
{'jajca': 2, 'moka': 400}

Uradna rešitev

def potrebnoKupiti(recept, shramba):
    '''vrne slovar sestavin s pripadajočimi količinami, ki jih moramo še dokupiti, da bomo
      lahko skuhali jed po danem receptu.'''
    kupiti = dict()
    for sestavina, kolicina in recept.items():
        razlika = kolicina - shramba.get(sestavina, 0) # če sestavine še nimamo, je enako, kot če jo imamo 0!
        if razlika > 0:
            kupiti[sestavina] = razlika
    return kupiti

Antipalindromi

1. podnaloga

Niz je antipalindrom, kadar ima znake na vseh mestih različne od svojega obrata. Tako je beseda mama antipalindrom, saj se noben znak ne ujema z znakom na istem mestu v besedi amam, beseda anketa pa ni antipalindrom, saj ima prvem in zadnjem mestu enako črko kot njen obrat atekna.

Sestavite funkcijo jeAntipalindrom(niz), ki vrne True, če je niz antipalindrom, in False če ni.

Uradna rešitev

def jeAntipalindrom(niz):
    '''Ali je niz antipalnidrom'''
    dolNiz = len(niz)
    if dolNiz % 2 == 1:  # vsi lihi nizi zagotovo niso antipalidromi!
        return False 
    for ind in range(dolNiz // 2): # preverimo prvih pol znakov (pazi 
        if niz[ind] == niz[dolNiz - 1 - ind] : # primerjamo znake začetnega in končnega dela
            return False       
    return True # vsi Testi so bili uspešni


def jeAntipalindromV2(niz):
    '''Ali je niz antipalnidrom'''
    # uporaba naprednejših metod
    # V dokumentaciji si oglej all in zip
    return all(z1 != z2 for z1, z2 in zip(niz, niz[::-1]))

2. podnaloga

Sestavite funkcijo vsebovaniAntipalindromi(niz), ki vrne množico vseh strnjenih podnizov niza niz, ki so antipalindromi.

Uradna rešitev

def vsebovaniAntipalindromi(niz):
    '''Vrne množico podnizov niza niz, ki so antipalindromi'''
    antipalindromi = set()
    # naredimo vse možne podnize
    for i in range(len(niz)):
        for j in range(i + 1, len(niz)+1):
            podniz = niz[i:j]
            # uporabimo funkcijo gornje naloge
            if jeAntipalindrom(podniz): # je anitiPalindrom, ga dodamo
                antipalindromi.add(podniz)
    return antipalindromi

Hatebook

Za razliko od običajnih družabnih omrežij, deluje nedružabno omrežje Hatebook tako, da si v omrežje vsak dodaja svoje sovražnike. Omrežje predstavimo s slovarjem, pri čemer so ključi osebe, vrednosti pa množice oseb, ki jih te osebe sovražijo.

1. podnaloga

Sestavite funkcijo seSovrazita(omrezje, oseba1, oseba2), ki vrne True, kadar osebi sovražita druga drugo, in False sicer.

Uradna rešitev

def seSovrazita(omrezje, oseba1, oseba2):
    '''Ali se osebi sovražita'''
    # oba ključa morata biti v seznamu vrednosti za drug ključ!
    return oseba1 in omrezje[oseba2] and oseba2 in omrezje[oseba1]

2. podnaloga

Sestavite funkcijo kdoSovrazi(omrezje, oseba), ki vrne množico oseb, ki v danem omrežju sovražijo dano osebo.

Uradna rešitev

def kdoSovrazi(omrezje, oseba):
    '''vrne množico oseb, ki v danem omrežju sovražijo dano osebo '''
    kdoSovraži = set()
    for sovrag, sovrazniki in omrezje.items():
        if oseba in sovrazniki:
            kdoSovraži.add(sovrag)
    return kdoSovraži

def kdoSovraziV2(omrezje, oseba):
    '''vrne množico oseb, ki v danem omrežju sovražijo dano osebo '''
    # uporaba izpeljanih množic (set comprehension)
    return {sovrag for sovrag, sovrazniki in omrezje.items()
            if oseba in sovrazniki}

3. podnaloga

Sestavite funkcijo nesrecniki(omrezje), ki vrne množico oseb, ki sovražijo same sebe.

Uradna rešitev

def nesrecniki(omrezje):
    '''Vrne množico oseb, ki sovražijo sebe'''
    mnNesrečnikov = set()
    for oseba, sovrazniki in omrezje.items():
        if oseba in sovrazniki:
            mnNesrečnikov.add(oseba)
    return mnNesrečnikov

def nesrecnikiV2(omrezje):
    '''Vrne množico oseb, ki sovražijo sebe'''
    # uporaba izpeljanih množic
    return {oseba for oseba, sovrazniki in omrezje.items()
            if oseba in sovrazniki}

4. podnaloga

Sestavite funkcijo najboljZadrti(omrezje), ki vrne množico vseh oseb, ki v danem omrežju sovražijo največ oseb.

Uradna rešitev

def najboljZadrti(omrezje):
    '''vrne množico vseh oseb, ki v danem omrežju sovražijo največ oseb'''
    najvec = 0
    for sovrazniki in omrezje.values():
        najvec = max(len(sovrazniki), najvec) # večjega od trenutnega kandidata in naj doslej
    # in še izpeljanih množic
    mnZadrtih = set()
    for oseba, sovrazniki in omrezje.items():
        if len(sovrazniki) == najvec:
            mnZadrtih.add(oseba)
    return mnZadrtih

def najboljZadrtiV2(omrezje):
    '''vrne množico vseh oseb, ki v danem omrežju sovražijo največ oseb'''
    #uporaba izpeljaniega ponovnika
    najvec = max(len(sovrazniki) for sovrazniki in omrezje.values())
    # in še izpeljanih množic
    return {oseba for oseba, sovrazniki in omrezje.items()
            if len(sovrazniki) == najvec}

Unija slovarjev

1. podnaloga

Sestavite funkcijo unijaSlovarjev(seznam_slovarjev), ki bo iz danega seznama slovarjev sestavila nov slovar, ki bo predstavljal unijo posameznih slovarjev. Vrednosti ključev v uniji slovarjev naj bodo seznami vrednosti, ki pripadajo enakim ključem iz vhodnih slovarjev. Vrednosti naj bodo v seznamih zapisane v enakem vrstnem redu, kot nastopajo v seznamu slovarjev. Zgled:

>>> unija_slovarjev([{1: 2, 5: 0}, {2: 3, 5: 6, 7: 3}, {2: 3, 8: 1, 5: 4}])
{1: [2], 5: [0, 6, 4], 2: [3, 3], 7:[3], 8:[1]}

Uradna rešitev

def unijaSlovarjev(seznamSlovarjev):
    '''Vrnemo slovar, ki je unija slovarjev'''
    novSlovar = dict()
    for slovar in seznamSlovarjev: # obdelamo vse slovarje
        for kljuc in slovar:
            if kljuc in novSlovar: # če se je ta ključ že pojavil
                novSlovar[kljuc].append(slovar[kljuc]) # dodamo njegovo vrednost
            else:
                novSlovar[kljuc] = [slovar[kljuc]] # sicer pa je to nov ključ
    return novSlovar

Električne naprave

Patrik je za vse električne naprave, ki jih ima doma, ugotovil ime proizvajalca in podatke shranil v slovar. Zgled takega slovarja:

naprave = {
    'hladilnik': 'Gorenje', 'pralni stroj': 'Whirlpool',
    'kavni mlinček': 'Bosch', 'mikrovalovna pečica': 'Gorenje',
    'parni čistilnik': 'Philips', 'laserski tiskalnik': 'Lexmark',
    'sušilnik las': 'Philips'
}

Njegov sosed Darko pa je iz čistega dolgčasa sestavil slovar, v katerem so ključi naprave, vrednosti pa kategorije, kamor te naprave sodijo. Zgled:

kategorije = {
    'hladilnik': 'bela tehnika', 'parni čistilnik': 'sesalniki',
    'grelnik vode': 'kuhinjski aparati', 'pralni stroj': 'bela tehnika',
    'sušilnik las': 'nega las', 'mikrovalovna pečica': 'kuhinjski aparati', 
    'laserski odstranjevalec dlačic': 'brivniki in depilatorji'
}

1. podnaloga

Patrik in Darko bi rada združila podatke in za vsako blagovno znamko, ki se pojavi v Patrikovem slovarju, ugotovila, katere kategorije naprav "pokriva" glede na Darkov slovar. Napišite funkcijo blagovne_znamke(naprave, kategorije), ki vrne slovar, kjer so ključi imena proizvajalcev, njihove pripadajoče vrednosti pa so množice kategorij, s katerimi se proizvajalec ukvarja.

Naj bosta slovarja naprave in kategorije enaka kot zgoraj. Zgled:

>>> blagovne_znamke(naprave, kategorije)
{'Lexmark': set(), 'Philips': {'sesalniki', 'nega las'}, 'Whirlpool': {'bela tehnika'},
 'Gorenje': {'bela tehnika', 'kuhinjski aparati'}, 'Bosch': set()}

Bodite pozorni na to, da se lahko v Patrikovem slovarju pojavijo tudi naprave, ki jih Darko nima v svojem slovarju, in obratno.

Uradna rešitev

def blagovne_znamke(naprave, kategorije):
    '''vrne slovar, kjer so ključi imena proizvajalcev, njihove pripadajoče vrednosti
       pa so množice kategorij, s katerimi se proizvajalec ukvarja.'''
    blagZnamke = dict()
    for naprava, znamka in naprave.items():
        if znamka not in blagZnamke:
            blagZnamke[znamka] = set() # nova znamka, začnemo s prazno množico
        if naprava in kategorije:
            blagZnamke[znamka].add(kategorije[naprava]) # dodamo vse ustrezne kategorije
    return blagZnamke

Ključ z največjo vrednostjo

Dan je slovar, ki slika ključe xi (ključi so nizi) v celoštevilske vrednosti vi, recimo

   {'foo':1, 'bar':7, 'baz':100, 'qux':20, 'quux':30}

1. podnaloga

Sestavi funkcijo ključZNajVrednostjo(sl), ki sprejme tak slovar in vrne tisti ključ xi, ki ima največjo pripadajočo vrednost vi. Če bi na primer poklicali funkcijo s prejšnjim slovarjem, bi dobili rezultat 'baz'. Če je slovar prazen, vrni None. Predpostavi, da je le en ključ z največjo vrednostjo.

Uradna rešitev

def ključZNajVrednostjo(sl):
    ''' vrne tisti ključ `xi`, ki ima največjo pripadajočo vrednost `vi`.'''
    if not sl:  # če je prazen
        return None
    # za kandidata vzamemo vrednost prvega iz slovarja
    for kl, vr in sl.items():
        najVr = vr
        najKljuč = 'Žal bom izginil'
        break  # rabimo le prvega
    # sedaj pa zares
    for kl, vr in sl.items():
        if vr >= najVr:  # našli smo boljšega
            najVr = vr
            najKljuč = kl
    return najKljuč

2. podnaloga

Sedaj pa spustimo omejitev, da obstaja le en ključ z največjo vrednostjo.

Sestavi funkcijo seznamKljučevZNajVrednostjo(sl), ki vrne po abecedi urejen seznam vseh ključev z največjo vrednostjo. Če je slovar prazen, vrni prazen seznam.

Uradna rešitev

def seznamKljučevZNajVrednostjo(sl):
    ''' vrne po abecedi urejen seznam tisti ključev `xi`, ki imajo
        največjo pripadajočo vrednost `vi`.'''
    if not sl:  # če je prazen
        return []
    # za kandidata vzamemo vrednost prvega iz slovarja - 1
    for kl, vr in sl.items():
        najVr = vr - 1
        najKljuč = []
        break  # rabimo le prvega
    # sedaj pa zares
    for kl, vr in sl.items():
        if vr > najVr:  # našli smo boljšega
            najVr = vr
            najKljuč = [kl]
        elif vr == najVr:  # našli smo enako dobrega
            najKljuč.append(kl)
    return sorted(najKljuč)

Ljubezen nam je vsem v pogubo I

prosto po Tavčarju ;-) ali po Galetu

Socialno omrežje zaljubljenosti podamo s slovarjem, ki ime osebe preslika v seznam vseh, v katere je oseba zaljubljena (ena oseba je lahko zaljubljena v več oseb). Na primer, slovar

s = {'Ana' : ['Bine','Cene'],
     'Bine' : [],
     'Cene' : ['Bine', 'Cene'],
     'Davorka' : ['Davorka'],
     'Eva' : ['Bine']}

nam pove, da je Ana zaljubljena v Bineta in Cenete, Bine ni zaljubljen, Cene ljubi Bineta in samega sebe, Davorka samo sebe in Eva Bineta.

1. podnaloga

Sestavite funkcijo narcisoidi(d), ki sprejme slovar zaljubljenih in vrne po abecedi urejen seznam tistih, ki ljubijo same sebe.

Uradna rešitev

def narcisoidi(d):
    '''Vrne po abecedi urejen seznam narcisoidov'''
    sezNar = []
    for oseba in d:
        if oseba in d[oseba]: # ta bo pravi!
            sezNar.append(oseba)
    return sorted(sezNar)

def narcisoidiV2(d):
    '''Vrne po abecedi urejen seznam narcisoidov'''
    # uporabimo izpeljane sezname (list comprehension)
    return sorted([oseba for oseba in d if oseba in d[oseba]])

2. podnaloga

Sestavite funkcijo ljubljeni(d), ki sprejme slovar zaljubljenih in vrne po abecedi urejen seznam tistih, ki so ljubljeni.

Uradna rešitev

def ljubljeniV2(d):
    '''Vrne po abecedi urejen _seznam_ tistih, ki so ljubljeni'''
    # naredimo s seznamom
    seznamOseb =  list()
    for oseba in d: # za vse osebe
        for ljubljen in d[oseba]: # dodamo njihove ljubljene (če je potrebno)
            if ljubljen not in seznamOseb: # če še niso
                seznamOseb.append(ljubljen)
    return sorted(seznamOseb)

def ljubljeni(d):
    '''Vrne po abecedi urejen _seznam_ tistih, ki so ljubljeni'''
    mnLjubljenih =  set()
    for oseba in d: # za vse osebe
        mnLjubljenih.update(d[oseba]) # dodamo vse ljubljene te osebe
    return sorted(mnLjubljenih) # sorted vrne urejen seznam - argument je lahko poljubni iterator

3. podnaloga

Sestavite funkcijo pari(d), ki sprejme slovar zaljubljenih in vrne seznam vseh parov, ki so srečno ljubljeni. Vsak par naj se pojavi samo enkrat in sicer tako, da je sta zaljubljenca našteta po abecedi. Na primer, če sta Ana in Bine zaljubljena, dodamo par ('Ana','Bine').

Uradna rešitev

def pari(d):
    '''Po abecedi urejen par srečno ljubljenih - torej takioh, ki ljubijo osebo, ki ljubi njih'''
    seznamParov = []
    for oseba in d:
        # za vsako osebo, ki jo ljubi, pogledamo, če ta ljubi njega
        for ljubljeni in d[oseba]:
            if oseba in d[ljubljeni] :
                # ga bomo dodali
                urejenPar = tuple(sorted([oseba,ljubljeni]))
                # a le , če že ni notri
                if urejenPar not in seznamParov:  # namig - namesto seznama bi lahko uporabili množico in bi ta stavek if odpadel
                    seznamParov.append(urejenPar)
    return sorted(seznamParov)

4. podnaloga

Sestavite funkcijo ustrezljivi(oseba, d), ki sprejme ime osebe ter slovar zaljubljenih, vrne pa po abecedi urejen seznam vseh ljudi, ki so do dane osebe še posebej ustrežljivi. Posebej ustrežljivi so seveda za to, ker so bodisi zaljubljeni v dano osebo, bodisi so zaljubljeni v osebo, ki je posebej ustrežljiva do nje, in tako naprej.

Na primer, če imamo slovar

s = {'Ana' : ['Bine', 'Cene'],
     'Bine' : ['Ana'],
     'Cene' : ['Bine'],
     'Davorka' : ['Davorka'],
     'Eva' : ['Bine']}

so do Ceneta posebej ustrežljivi Ana (ki je zaljubljena vanj), Bine (ki je zaljubljen v Ano), Eva (ki je zaljubljena v Bineta), ter seveda Cene, ki je zaljubljen v Evo.

Uradna rešitev

def ustrezljiviV2(oseba, d):
    '''vrne po abecedi urejen _seznam_ vseh ljudi, ki so do dane osebe še posebej ustrežljivi'''
    # seznam, v katerega nabiramo ustrežljive osebe
    ustrezljivi = []
    # najprej dodamo tiste, ki ljubijo prvo osebo
    dodani = [o for o in d if oseba in d[o]]
    # dokler smo koga dodali, dodajamo ustrežljive
    while dodani:
        for nekdo in dodani:
            if nekdo not in ustrezljivi: # če ga še ni noter
                ustrezljivi.append(nekdo)
        # sedaj pa dodajamo tiste, ki ljubijo nazadnje dodane osebe
        dodani = [o for o in d for dodan in dodani
                  if dodan in d[o] and o not in ustrezljivi]
    return sorted(ustrezljivi)

def ustrezljivi(oseba, d):
    '''vrne po abecedi urejen _seznam_ vseh ljudi, ki so do dane osebe še posebej ustrežljivi'''
    # seznam, v katerega nabiramo ustrežljive osebe
    ustrezljivi = []
    # najprej dodamo tiste, ki ljubijo prvo osebo
    dodani = []
    for nekdo in d:
        if oseba in d[nekdo]:
            dodani.append(nekdo)
    # dokler smo koga dodali, dodajamo ustrežljive
    while dodani:
        for nekdo in dodani:
            if nekdo not in ustrezljivi: # če ga še ni noter
                ustrezljivi.append(nekdo)
        # sedaj pa dodajamo tiste, ki ljubijo nazadnje dodane osebe
        noviDodani = []
        for o in d:
            for nekdo in dodani:
                if nekdo in d[o] and o not in ustrezljivi:
                    noviDodani.append(o)
        dodani = noviDodani[:]
    return sorted(ustrezljivi)

Rimski imperij vrača udarec

Pri tej nalogi boste napisali funkcijo, ki bo za dano število vrnila niz z ustrezno rimsko številko. Nato boste napisali še funkcijo, ki bo rimsko številko spremenila nazaj v število.

Preden začnete, si na oglejte članek o rimskih številkah na Wikipediji: Rimske številke.

1. podnaloga

Napišite funkcijo vRimsko(stevilo), ki kot argument dobi celo število med 1 in 3999 (vključno z 1 in 3999). Funkcija naj sestavi in vrne niz, ki vsebuje rimsko številko, ki predstavlja število stevilo. Zgled:

>>> vRimsko(2013)
'MMXIII'

Uradna rešitev

def vRimsko(stevilo):
    '''Iz 'običajnega' zapisa števila med 1 in 3999 naredimo rimski zapis števila
    '''
    tabelaRimskih = [ ['', 'I', 'II', 'III', 'IV', 'V', 'VI', 'VII', 'VIII', 'IX'],
                      ['', 'X', 'XX', 'XXX', 'XL', 'L', 'LX', 'LXX', 'LXXX', 'XC'],
                      ['', 'C', 'CC', 'CCC', 'CD', 'D', 'DC', 'DCC', 'DCCC', 'CM'],
                      ['', 'M', 'MM', 'MMM']]
    rimsko = ''
    for i in range(4):
        rimsko = tabelaRimskih[i][stevilo%10] + rimsko
        stevilo //= 10
    return rimsko

2. podnaloga

Napišite še funkcijo vArabsko(niz), ki bo dobila niz niz, ki predstavlja rimsko številko. Funkcija naj naredi ravno obratno kot funkcija vRimsko, tj. vrne naj ustrezno število, ki ga predstavlja dana rimska številka. Če niz ne predstavlja veljavnege rimske številke, naj funkcija vrne None. Zgled:

>>> vArabsko('MMXIII')
2013

Nasvet: Najprej sestavi slovar, ki kot ključe vsebuje rimske številke, kot vrednosti pa ustrezna števila. Potem le uporabi ta slovar.

Uradna rešitev

def vArabsko(niz):
    '''Iz rimskega zapisa naredimo arabski zapis števila
       Če ne gre, vrnemo None.
    '''
    tabelaRimskih = [ ['', 'I', 'II', 'III', 'IV', 'V', 'VI', 'VII', 'VIII', 'IX'],
                  ['', 'X', 'XX', 'XXX', 'XL', 'L', 'LX', 'LXX', 'LXXX', 'XC'],
                  ['', 'C', 'CC', 'CCC', 'CD', 'D', 'DC', 'DCC', 'DCCC', 'CM'],
                  ['', 'M', 'MM', 'MMM']]
    slovarRimskih = {vRimsko(i):i for i in range(1, 4000)}

    if niz not in slovarRimskih:
        return None
    return slovarRimskih[niz]

Rodovniki

Ukvarjali se bomo z rodovniki (Celjskih grofov in drugih). Rodovnik imamo podan kot slovar, kjer je ključ ime "glave rodbine" vrednost pa seznam imen otrok. Recimo:

rodovnik =
 {'Ulrik I.': ['Viljem'], 'Margareta': [], 'Herman I.': ['Herman II.', 'Hans'],
  'Elizabeta II.': [], 'Viljem': ['Ana Poljska'], 'Elizabeta I.': [],
  'Ana Poljska': [], 'Herman III.': ['Margareta'], 'Ana Ortenburška': [],
  'Barbara': [], 'Herman IV.': [], 'Katarina': [], 'Friderik III.': [],
  'Herman II.': ['Ludvik', 'Friderik II.', 'Herman III.', 'Elizabeta I.', 'Barbara'],
  'Ulrik II.': ['Herman IV.', 'Jurij', 'Elizabeta II.'], 'Hans': [], 'Ludvik': [],
  'Friderik I.': ['Ulrik I.', 'Katarina', 'Herman I.', 'Ana Ortenburška'],
  'Friderik II.': ['Friderik III.', 'Ulrik II.'], 'Jurij': []}
 rodovnik['Friderik II.']

nam torej vrne

  ['Friderik III.', 'Ulrik II.']

1. podnaloga

Število otrok

Sestavi funkcijo kolikoOtrok(ime, rodovnik), ki za dano ime in rodovnik vrne število otrok te osebe, oz None, če osebe ni v rodovniku.

Uradna rešitev

def kolikoOtrok(ime, rodovnik) :
    ''' koliko otrok ima oseba z imenom ime '''
    if ime not in rodovnik:
        return None
    return len(rodovnik[ime])

2. podnaloga

Število potomcev

Sestavi funkcijo kolikoPotomcev(ime, rodovnik), ki za dano ime in rodovnik vrne število potomcev te osebe. Če osebe ni v rodovniku, vrni None

Uradna rešitev

def kolikoPotomcev(ime, rodovnik) :
    ''' koliko potomcev ima oseba z imenom ime '''
    if ime not in rodovnik: # če je slučajno ni
        return None
    otroci = rodovnik[ime]
    kolikoJihJe = len(otroci) # potomci so otroci
    for oseba in otroci: # in vsi potomci otrok
        kolikoJihJe += kolikoPotomcev(oseba, rodovnik)
    return kolikoJihJe

3. podnaloga

Je v rodbini?

Sestavi funkcijo jeTaVRodbini(ime, glavaRodbine, rodovnik), ki ugotovi, ali je oseba z imenom ime v rodbini osebe glavaRodbine.

Uradna rešitev

def jeTaVRodbini(ime, glavaRodbine, rodovnik) :
    ''' Ali je oseba z imenom ime v rodbini osebe glavaRodbine '''
    if ime == glavaRodbine: # če je to že kar "šef"
        return True
    # je morda med otroci
    otroci = rodovnik[glavaRodbine]
    if ime in otroci :  # pravzaprav je ta stavek if odveč. Zakaj? Premisli!
        return True
    # je morda v rodbini otrok?
    for oseba in otroci :
        if jeTaVRodbini(ime, oseba, rodovnik) :
            return True
    # ni bil nikjer, torej ...
    return False

4. podnaloga

Kdo se podpisuje najdlje časa?

Sestavi funkcijo najdaljsiPodpis(glavaRodbine, rodovnik), ki ugotovi, kdo v rodbini osebe glavaRodbine ima najdaljše ime za podpis (torej kompletno ime).

Uradna rešitev

def najdaljsiPodpis(glavaRodbine, rodovnik) :
    ''' kdo v rodbini osebe glavaRodbine ima najdaljše ime. '''
    najIme = glavaRodbine  # morda je to kar glava rodbine
    # je morda v rodbini otrok?
    otroci = rodovnik[glavaRodbine]
    for oseba in otroci :
        najMedOsebo = najdaljsiPodpis(oseba, rodovnik)
        if len(najMedOsebo) > len(najIme) :
            najIme = najMedOsebo
    return najIme

5. podnaloga

Kdo ima najkrajše ime?

Sestavi funkcijo najkrajseIme(glavaRodbine, rodovnik), ki ugotovi, kdo v rodbini osebe glavaRodbine ima najkrajše ime. (šteje samo krstno ime, brez "Ortenburga" in "Celja" ter brez številk)?

Uradna rešitev

def najkrajseIme(glavaRodbine, rodovnik) :
    ''' kdo v rodbini osebe glavaRodbine ima najkrajse ime. '''
    # morda je to kar glava rodbine
    najIme = glavaRodbine.split()[0]  # izrabimo dejstvo, da je "pravo" ime takoj na začetku ...
    # je morda v rodbini otrok?
    otroci = rodovnik[glavaRodbine]
    for oseba in otroci :
        najMedOsebo = najkrajseIme(oseba, rodovnik)
        if len(najMedOsebo) < len(najIme) :
            najIme = najMedOsebo
    return najIme

6. podnaloga

Globina rodbine

"Globino" rodbine definiramo tako: če nekdo nima otrok, je globina njegove rodbine 1. Če ima otroka, ta pa nima vnukov (ali celo več otrok, ti pa nimajo vnukov), je globina rodbine 2. Če nekdo ima vnuke, vendar nobenega pravnuka, je globina njegove rodbine 3.

Sestavi funkcijo globina(glavaRodbine, rodovnik), ki vrne globino rodbine osebe glavaRodbine v rodovniku rodovnik

Uradna rešitev

def globina(glavaRodbine, rodovnik):
    '''Kakšna je globina rodbine osebe glavaRodbine'''
    # če nima otrok, je na globini 1
    if rodovnik[glavaRodbine] == []:
        return 1
    # ima vsaj enega otroka
    # potrebujemo globine vseh otrok te glaveRodbine
    glOtrok = []
    for otrok in rodovnik[glavaRodbine]:
        # koliko je globina za tega otroka
        glOtroka = globina(otrok, rodovnik)
        glOtrok.append(glOtroka)
    # zanima nas le največja
    najGlOtrok = max(glOtrok)
    # globina glave rodbine je za 1 večja od tega maksimuma
    return 1 + najGlOtrok

def globinaV2(glavaRodbine, rodovnik):
    '''Kakšna je globina rodbine osebe glavaRodbine
       brez uporabe funkcije max '''
    # če nima otrok, je na globini 1
    if rodovnik[glavaRodbine] == []:
        return 1
    # ima vsaj enega otroka
    # potrebujemo maksimalno globino od vseh otrok te glaveRodbine
    najGlOtrok = 0 # ker so vse globine poz. števila, je začetni kandidat lahko 0
    for otrok in rodovnik[glavaRodbine]:
        # koliko je globina za tega otroka
        glOtroka = globinaV2(otrok, rodovnik)
        if glOtroka > najGlOtrok: # našli smo boljšega kandidata
            najGlOtrok = glOtroka
    # globina glave rodbine je za 1 večja od tega maksimuma
    return 1 + najGlOtrok

def globinaV3(oseba, rodovnik):
    otroci = rodovnik[oseba]
    if otroci: # če imamo otroke, je naša globina za 1 večja od naj globine naših otrok
        return 1 + max(globinaV3(otrok, rodovnik) for otrok in otroci)
    else: # drugače smo na globini 1
        return 1